package com.my.algorithmlearning.leetcode;

import com.my.algorithmlearning.entity.ListNode;
import org.springframework.util.Assert;

/**
 * @ClassName GetIntersectionNode
 * @Description GetIntersectionNode
 * @Author wanghaiwei
 * @Date 2022/12/6 17:04
 */
public class GetIntersectionNode {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode currA = headA, currB = headB;
        int sizeA = 0;
        int sizeB = 0;
        while(true) {
            if(currA ==null && currB ==null) {
                break;
            }
            if (currA != null) {
                sizeA++;
                currA = currA.next;
            }
            if(currB != null) {
                sizeB++;
                currB = currB.next;
            }
        }
        ListNode currShort;
        ListNode currLong;
        int start = 0;
        int end = 0;
        if(sizeA > sizeB) {
            currShort = headB;
            currLong = headA;
            start = sizeB-sizeA;
            end = sizeB;
        }else {
            currShort = headA;
            currLong = headB;
            start = sizeA-sizeB;
            end = sizeA;
        }
        int i;
        for (i = start; i < end; i++){
            if (i < 0) {
                currLong = currLong.next;
            }else if(currLong == currShort){
                return currLong;
            }else {
                currLong = currLong.next;;
                currShort = currShort.next;
            }
        }
        return null;
    }

    public ListNode generateIntersectListNode(int[] separatePart, ListNode commonPart) {
        ListNode root = this.generateListNode(separatePart);
        if (commonPart != null) {
            root.next = commonPart;
        }
        return root;
    }

    public ListNode generateListNode(int[] array) {
        ListNode root = new ListNode(array[0]);
        for (int i = 1; i < array.length; i++) {
            root.next = new ListNode(array[i]);
        }
        return root;
    }

    public static void main(String[] args) {
        GetIntersectionNode solution = new GetIntersectionNode();
        ListNode commonPart1 = solution.generateListNode(new int[]{8,4,5});
        ListNode rootA1 = solution.generateIntersectListNode(new int[]{4,1}, commonPart1);
        ListNode rootB1 = solution.generateIntersectListNode(new int[]{5,6,1}, commonPart1);
        Assert.isTrue(solution.getIntersectionNode(rootA1,rootB1) == commonPart1, "listA = [4,1,8,4,5], listB = [5,6,1,8,4,5]计算错误");

        ListNode commonPart2 = solution.generateListNode(new int[]{2,4});
        ListNode rootA2 = solution.generateIntersectListNode(new int[]{1,9,1}, commonPart2);
        ListNode rootB2 = solution.generateIntersectListNode(new int[]{3}, commonPart2);
        Assert.isTrue(solution.getIntersectionNode(rootA2,rootB2) == commonPart2, "listA = [1,9,1,2,4], listB = [3,2,4]计算错误");


        ListNode rootA3 = solution.generateIntersectListNode(new int[]{1,9,1}, null);
        ListNode rootB3 = solution.generateIntersectListNode(new int[]{3}, null);
        Assert.isTrue(solution.getIntersectionNode(rootA3,rootB3) == null, "listA = [2,6,4], listB = [1,5]计算错误");

        ListNode commonPart4 = solution.generateListNode(new int[]{1});
        Assert.isTrue(solution.getIntersectionNode(commonPart4,commonPart4) == commonPart4, "listA = [1], listB = [1]计算错误");
    }

}
